After adding vertex $C$ and updating the frontier, the algorithm's core loop begins again. We once more make the greedy choice by selecting the cheapest edge from our updated priority queue.

  • The new minimum-weight edge is (1, 'C', 'B'). Since vertex $B$ is not yet in our MST, this is a valid connection.
  • We add vertex $B$ to the mst_vertices set and the edge $(C, B)$ to our list of MST edges.
  • Finally, we explore from our new vertex, $B$, to update the frontier again.
  • We check $B$'s neighbors: $A$, $C$, and $D$. Neighbors $A$ and $C$ are ignored as they are already in the MST.
  • Neighbor $D$ is unvisited, so we add the edge $(B, D)$ with weight 5 to the priority queue.
  • The priority queue now holds all known, safe edges that cross the "cut" from our growing tree to the rest of the graph.
Python: Prim's Algorithm - Second Iteration
1import heapq
2
3graph = {
4    'A': {'B': 4, 'C': 3}, 'B': {'A': 4, 'C': 1, 'D': 5},
5    'C': {'A': 3, 'B': 1, 'D': 2, 'E': 6}, 'D': {'B': 5, 'C': 2, 'E': 8, 'F': 7},
6    'E': {'C': 6, 'D': 8, 'F': 9}, 'F': {'D': 7, 'E': 9}
7}
8# State from previous slide
9mst_vertices = {'A', 'C'}
10priority_queue = [(1, 'C', 'B'), (2, 'C', 'D'), (4, 'A', 'B'), (6, 'C', 'E')]
11heapq.heapify(priority_queue) # Ensure it's a valid heap for the demo
12mst_edges = [('A', 'C', 3)]
13
14# Main loop - Second iteration
15if priority_queue:
16    # 1. Make the next greedy choice
17    weight, u, v = heapq.heappop(priority_queue)
18
19    # 2. Check if the new vertex is already in the MST
20    if v not in mst_vertices:
21        # 3. Add the new vertex and edge to our MST
22        mst_vertices.add(v)
23        mst_edges.append((u, v, weight))
24
25        # 4. Update the frontier with new edges from B
26        for neighbor, weight in graph[v].items():
27            if neighbor not in mst_vertices:
28                heapq.heappush(priority_queue, (weight, v, neighbor))